package syf.binaryranktree;


public class BinaryRankTree {
    public static void main(String[] args) {
        int[] arr={7,3,10,12,5,1,9,2};
        BinaryTree binaryTree=new BinaryTree();
        for (int i : arr) {
            binaryTree.add(new Node(i));
        }
        binaryTree.preShow();
        System.out.println("==========删除结点==========");
        binaryTree.deleteNode(3);
        binaryTree.preShow();
    }
}
//二叉排序树
class BinaryTree{
    Node root;
    //为树添加节点
    public void add(Node node){
        if (root!=null){
            root.addNode(node);
        }else {
            root=node;
        }
    }
    //中序遍历
    public void preShow(){
        if (root!=null){
            root.preShow();
        }else {
            System.out.println("为空");
        }
    }
    //删除节点
    //1、查找要删除的结点
    public Node searchDelTarget(int value){
        if (root==null){
            return null;
        }else {
            return root.searchDelTarget(value);
        }
    }
    //2、查找要删除节点的父节点
    public Node searchDelParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchDelParent(value);
        }
    }
    //删除结点的方法
    public void deleteNode(int value){
        if (root==null){
            System.out.println("空结点");
        }else {
            if (root.left==null&&root.right==null){
                root=null;
                return;
            }
            //要删除的结点
            Node target=searchDelTarget(value);
            //要查找的结点的父结点
            Node parent=searchDelParent(value);
            if (target==null) {
                System.out.println("没有要删除的结点");
            }else {
                if (parent!=null){
                    //要删除的为叶子结点
                    if (target.left==null&&target.right==null){
                        if (parent.left!=null&&parent.left==target){
                            parent.left=null;
                        }else{
                            parent.right=null;
                        }
                    }
                    //被删除的结点有一个子节点
                    if (target.left==null&&target.right!=null||target.right==null&&target.left!=null){
                        if (target.left!=null&&parent.left==target){//要删除结点的左结点不为空，且为父节点的左结点
                            parent.left=target.left;
                        }else if (target.right!=null&&parent.left==target){//要删除结点右左结点不为空，且为父节点的左结点
                            parent.left=target.right;
                        }else if (target.left!=null&&parent.right==target){//要删除结点的左结点不为空，且为父节点的右结点
                            parent.right=target.left;
                        }else if (target.right!=null&&parent.right==target){//要删除结点的右结点不为空，且为父节点的右结点
                            parent.right=target.right;
                        }
                    }
                    //被删除的结点有两个子节点
                    if (target.left!=null&&target.right!=null){
                        //向右找，找最小的或者向左找找最大的
                        //向右找,找最小
                        int minNodeVal = searchMin(target.right);
                        if (parent.left==target){
                            parent.left.value=minNodeVal;
                        }else {
                            parent.right.value=minNodeVal;
                        }
                    }
                }else {
                    if (target.left!=null&&target.right!=null){
                        //向右找，找最小的或者向左找找最大的
                        //向右找,找最小
                        target.value= searchMin(target.right);
                    }
                }
            }
        }
    }
    //找最小的

    /**
     * 找出
     * 删除
     * @param node 当作一个二叉树的新结点
     * @return 返回以node为根节点的值最小的结点
     */
    public int searchMin(Node node){
        Node target=node;
        while (target.left!=null){
            target= target.left;
        }
        deleteNode(target.value);
        return target.value;
    }
}
//节点
class Node{
    Node left;
    Node right;
    int value;
    public Node(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    //添加节点
    public void addNode(Node node){
        if (node!=null) {
            if (this.value < node.value) {//往右边放
                if (this.right == null) {//为空直接挂上去
                    this.right = node;
                } else {//不为空继续往左遍历
                    this.right.addNode(node);
                }
            }else {//当前节点的值小于等于
                if (this.left==null){
                    this.left=node;
                }else {//不为空继续遍历
                    this.left.addNode(node);
                }
            }
        }
    }

    //中序遍历
    public void preShow(){
        if (this.left!=null){
            this.left.preShow();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.preShow();
        }
    }
    //删除节点
    //1、先查找要删除的节点

    /**
     * 查找要删除节点
     * @param value 要删除的节点的值
     * @return 返回要删除的节点
     */
    public Node searchDelTarget(int value){
        //当前节点的值不等于要查找的值
        if (this.value!=value){
            //先向左递归
            if (this.value>value&&this.left!=null){//当前节点的值大于要查找的值左查找
                return this.left.searchDelTarget(value);
            }else if (this.value<=value&&this.right!=null){//在向右递归
                return this.right.searchDelTarget(value);
            }else {
                return null;
            }
        }else {
            return this;
        }
    }
    //2、查找要删除节点的父节点
    /**
     * @param value 要查找的节点的值
     * @return 要查找节点的父节点
     */
    public Node searchDelParent(int value){
        if (this.left!=null&&this.left.value==value||
            this.right!=null&&this.right.value==value){
            return this;
        }else{
            if (this.left!=null&&this.value>value){//当前节点的值大于要查找的值，且左结点不为空 ，左递归
                return this.left.searchDelParent(value);
            }else if (this.right!=null&&this.value<=value){//当前节点的小于等于要查找的值，且左结点不为空，右递归
                return this.right.searchDelParent(value);
            }else {//如果以上两个都没找到，则说明没有
                return null;
            }
        }
    }
}
